<html>
<head>
 
</head>
<body style="text-align=center;font-size:32px;">
<table align="center">
<tr><td><div id="problemNum" style='background-color:#999999;width:800;text-align:center;font-size:32px;'></div></td></tr>
<tr><td><div id="problemContent" style='word-wrap:break-word;background-color:#bbbbbb;width:800;text-align:left;font-size:20px;'></div></td></tr>
<tr><td><div id="result" style='word-wrap:break-word; color:#ffff22;font-size:48;background-color:#8855ff;width:800;text-align:center;'></div></td></tr>
<tr><td><div id="copyleft" style='word-wrap:break-word; color:#ffff22;font-size:18;background-color:#666666;width:800;text-align:right;'></div></td></tr>
<script language="javascript">
    //---------------------------------//
    // Project Euler 
    //
    // Author:thrombin
    //   Date:2015-12-09
    //---------------------------------//  
var p_order=8;//Problem Order
var num_str="73167176531330624919225119674426574742355349194934"
            +"96983520312774506326239578318016984801869478851843"
            +"85861560789112949495459501737958331952853208805511"
            +"12540698747158523863050715693290963295227443043557"
            +"66896648950445244523161731856403098711121722383113"
            +"62229893423380308135336276614282806444486645238749"
            +"30358907296290491560440772390713810515859307960866"
            +"70172427121883998797908792274921901699720888093776"
            +"65727333001053367881220235421809751254540594752243"
            +"52584907711670556013604839586446706324415722155397"
            +"53697817977846174064955149290862569321978468622482"
            +"83972241375657056057490261407972968652414535100474"
            +"82166370484403199890008895243450658541227588666881"
            +"16427171479924442928230863465674813919123162824586"
            +"17866458359124566529476545682848912883142607690042"
            +"24219022671055626321111109370544217506941658960408"
            +"07198403850962455444362981230987879927244284909188"
            +"84580156166097919133875499200524063689912560717606"
            +"05886116467109405077541002256983155200055935729725"
            +"71636269561882670428252483600823257530420752963450";
var problem_partA="The four adjacent digits in the 1000-digit number that have the greatest product are 9 x 9 x 8 x 9 = 5832.<br/>"
var problem_partB="<br/>Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?";
//solve the problem
//==============编程思路简介================
//  题目要求连续M个数字乘积里的最大值
//  等价于先求出所有连续M个数字的乘积，再求最大值
//      M=13为例，13=8+4+1=（1101）2
//      如果已经得到了M=1，M=4,M=8的连续乘积数组
//      那么 adj13 [j] = adj1[j] * adj4[j+1] * adj8[j+5]
//
//  总体来看，是采用的【动态规划】
//=====================================
var LEN=1000;
var M=13;//连续乘积的长度
var M_bin=(M).toString(2).split("").reverse().join("");//M二进制表示的逆序
var adj_prod=new Array(4);
var adj_prod_M=new Array(LEN-M);
var max=0,max_i=0;
 
//定义4个数组的大小
for(i=0;i<adj_prod.length;i++){
    adj_prod[i]=new Array(LEN-i);
}
//求连续1个数字乘积数组，也即原数组
for(i=0;i<LEN;i++){
    adj_prod[0][i]=parseInt(num_str[i]);    
}
//求2、4、8个连续数字乘积数组
for(i=1;i<adj_prod.length;i++){  
    for(j=0;j<LEN-Math.pow(2,i);j++){    
        adj_prod[i][j]=adj_prod[i-1][j]*adj_prod[i-1][j+Math.pow(2,i-1)];
    }
}
 
var step=0;
for(j=0;j<LEN-M;j++){    
    adj_prod_M[j]=1;
    step=0;
    for(i=0;i<adj_prod.length;i++){
        var tmp=parseInt(M_bin[i]);
        if(tmp>0){
        adj_prod_M[j]*=(adj_prod[i][j+step]);
        step+=(parseInt(Math.pow(2,i)));
        }
    }
    if(adj_prod_M[j]>max){max=adj_prod_M[j];max_i=j;}
}
//update browser
document.getElementById("problemNum").innerHTML="Project Euler-Problem "+p_order;
document.getElementById("problemContent").innerHTML=problem_partA+num_str.substring(0,max_i)+"<font color='red'>"+num_str.substring(max_i,max_i+13)+"</font>"+num_str.substring(max_i+13)+problem_partB;
document.getElementById("result").innerHTML="Answer:"+max+"("+max_i+")";
document.getElementById("copyleft").innerHTML="CopyLeft@Thrombin    2015";
</script>
</body>
</html>